import java.util.Stack;

class TreeNode {
    public char val;
    public TreeNode left;
    public TreeNode right;

    //TreeNode的构造方法
    public TreeNode(char val) {
        this.val = val;
    }
}

class MyBinaryTree {
     //人为拼接构造一颗二叉树的方法
     public TreeNode creatTree() {
         TreeNode A = new TreeNode('A');
         TreeNode B = new TreeNode('B');
         TreeNode C = new TreeNode('C');
         TreeNode D = new TreeNode('D');
         TreeNode E = new TreeNode('E');
         TreeNode F = new TreeNode('F');
         TreeNode G = new TreeNode('G');
         TreeNode H = new TreeNode('H');
         TreeNode I = new TreeNode('I');
         A.left = B;
         A.right = C;
         B.left = D;
         B.right = E;
         C.left = F;
         C.right = G;
         E.right = H;
         F.left = I;
         return A;//返回根节点A
     }

     //查找二叉树中是否包含值为key的节点的方法
     public TreeNode find(TreeNode root, char key) {
         //空节点返回空
         if (root == null) {
             return null;
         }
         //找到key值节点则返回
         if (root.val == key) {
             return root;
         }
         //递归左子树
         TreeNode leftVal = find(root.left, key);
         if (leftVal != null) {
             return leftVal;
         }
         //递归右子树
         TreeNode rightVal = find(root.right, key);
         if (rightVal != null) {
             return rightVal;
         }
         //程序全部运行结束说明没有招到值为key的节点
         return null;
     }

     //前序遍历方法
     public void preOrder(TreeNode root) {
         //空节点返回
         if (root == null) {
             return;
         }
         //打印根节点
         System.out.print(root.val + " ");
         //递归左子树
         preOrder(root.left);
         //递归右子树
         preOrder(root.right);

     }

     //中序遍历方法
     public void inOrder(TreeNode root) {
         //空节点返回
         if (root == null) {
             return;
         }
         //递归左子树
         inOrder(root.left);
         //打印根节点
         System.out.print(root.val + " ");
         //递归右子树
         inOrder(root.right);

     }

     //后序遍历方法
     public void postOrder(TreeNode root) {
         //空节点返回
         if (root == null) {
             return;
         }
         //递归左子树
         postOrder(root.left);
         //递归右子树
         postOrder(root.right);
         //打印根节点
         System.out.print(root.val + " ");

     }

     //获取树中的节点个数的方法
     public int getSize(TreeNode root) {
         //空节点返回0
         if (root == null) {
             return 0;
         }
         //递归左子树和右子树（+1为根节点个数）
         int size = 1 + getSize(root.left) + getSize(root.right);
         return size;
     }

     //获取二叉树中叶子节点个数的方法
     public int getLeafNodeCount(TreeNode root) {
         //空节点返回0
         if (root == null) {
             return 0;
         }
         //叶子节点返回1
         if (root.left == null && root.right == null) {
             return 1;
         }
         //递归左子树和右子树
         int count = getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
         return count;
     }

     //获取第k层(根节点层数为0)的节点个数的方法
     public int getKthLevelNodeCount(TreeNode root, int k) {
         //空节点返回0
         if (root == null) {
             return 0;
         } else if (k == 0) {
             //本层节点返回1
             return 1;
         }
         //递归左子树和右子树
         return getKthLevelNodeCount(root.left, k - 1) + getKthLevelNodeCount(root.right, k);

     }

     //获取二叉树的深度的方法
     public int getHight(TreeNode root) {
         //空节点返回-1
         if (root == null) {
             return -1;
         }
         //递归左子树
         int leftHeight = getHight(root.left);
         //递归右子树
         int rightHeight = getHight(root.right);
         //返回其中最大值
         return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
     }
 }
public class PreOrderNot {
    public void preOrderNot(TreeNode root){
        //创建一个新的栈
        Stack<TreeNode>stack=new Stack<>();
        //用cur记录当前遍历节点
        TreeNode cur=root;
        //根据先序遍历从下到上的顺序可知，若cur不为空或者栈不为空循环继续，使得cur从下至上遍历
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                //输出根节点值为最高优先级
                System.out.print(cur.val+" ");
                //向左子树遍历为次高优先级
                cur=cur.left;
            }
            //节点此时已打印完毕，弹出此节点,用top记录，以便向右子树遍历
            TreeNode top=stack.pop();
            //向右子树遍历为最低优先级
            cur=top.right;
        }

    }
    public static void main(String[] args) {
        MyBinaryTree myBinaryTree=new MyBinaryTree();
        PreOrderNot preOrderNot=new PreOrderNot();
        TreeNode root=myBinaryTree.creatTree();

        //递归方法实现前序遍历演示
        System.out.print("递归实现:  ");
        myBinaryTree.preOrder(root);
        System.out.println();
        System.out.println("*****************************");
        System.out.print("非递归实现:");
        preOrderNot.preOrderNot(root);
    }
}